

// pub trait I32Key {
//     fn key(&self) -> i64;
// } 

/// 从小到大排列的有序列表
pub struct ListSortedI64<TValue> {
    keys: Vec<(i64, usize)>,
    key_min: i64,
    key_max: i64,
    items: Vec<TValue>,
}

impl<TValue> ListSortedI64<TValue> {
    pub fn new() -> Self {
        Self {
            keys: vec![],
            items: vec![],
            key_min: i64::MAX,
            key_max: i64::MIN,
        }
    }
    pub fn len(&self) -> usize {
        self.items.len()
    }
    pub fn key_min(&self) -> i64 {
        self.key_min
    }
    pub fn key_max(&self) -> i64 {
        self.key_max
    }

    pub fn add(&mut self, key: i64, item: TValue) -> bool {
        let index = self.len();
        if index == 0 {
            self.key_min = key;
            self.key_max = key;
            self.keys.push((key, index));
            self.items.push(item);

            return true;
        }
        // 1. key is less than key_min
        if key < self.key_min {
            // debug!("List_Ordered::add: 添加的 {key} 比最小值 {} 小, 插入头部0位置.", self.key_min);
            self.keys.insert(0, (key, index));
            self.key_min = key;

            self.items.push(item);
            return true;
        };
        // 3. key is larger than key_max
        if key > self.key_max() {
            // debug!("List_Ordered::add: 添加的 {key} 比最大值 {} 小, 添加在尾部位置.", self.key_max);
            self.keys.push((key, index));
            self.key_max = key;
            
            self.items.push(item);
            return true;
        }
        // 2. key is between key_min and key_max
        // debug!("List_Ordered::add: 出现【后发先至】{} ==> {key}, 采用插入方法", self.key_max);
        let len = self.items.len();
        for idx in (0..len).rev() {
            let key_current = self.keys[idx].0;
            if key_current == key {
                // error!("List_Ordered::add: 重复添加 {key}");
                return false;
            }
            if key_current > key {
                continue;
            }
            // key_current < key
            // debug!("List_Ordered::add: 在 {key_current} 后面添加 {key}");
            self.keys.insert(idx + 1, (key, index));
            
            self.items.push(item);
            return true;
        }

        false
    }
    pub fn index_of(&self, key2find: i64) -> Option<usize> {
        match self.keys.binary_search_by(|x| x.0.cmp(&key2find)) {
            Ok(index_key) => Some(self.keys[index_key].1),
            Err(_) => {
                // error!("self.find_binary(key2find={}), not exists.", key2find);
                // 一般来说，如果是严格的从小到大，如果存在，肯定能找到
                // self.find_plain(key2find)
                None
            },
        }
    }
    pub fn get(&self, key2find: i64) -> Option<&TValue> {
        let index = self.index_of(key2find)?;
        self.items.get(index)
    }
    pub fn get_mut(&mut self, key2find: i64) -> Option<&mut TValue> {
        let index = self.index_of(key2find)?;
        self.items.get_mut(index)
    }
    
    pub fn iter_unsorted(&self) -> std::slice::Iter<'_, TValue> {
        self.items.iter()
    }

    pub fn iter_mut_unsorted(&mut self) -> std::slice::IterMut<'_, TValue> {
        self.items.iter_mut()
    }

    pub fn items_sorted_ref(&self) -> Vec<(i64, &TValue)> {
        let mut items = vec![];

        for (key, index) in self.keys.clone() {
            items.push((key, &self.items[index]));
        }

        items
    }

    // pub fn items_sorted(self) -> Vec<TValue> {
    //     let mut items = vec![];

    //     for (key, index) in self.keys.clone() {
    //         items.push(self.items[index]);
    //     }

    //     items
    // }

    // pub fn items_mut_sorted(&mut self) -> Vec<(i64, &mut TValue)> {
    //     let mut items = vec![];

    //     for (key, index) in self.keys.clone() {
    //         items.push((key, &mut self.items[index]));
    //     }

    //     items
    // }


}

